22 Discrete-Time MC

#MarkovChain #TransitionMatrix #CKEquation #Stationary

Problem of the week

A deck of $N$ cards. Each with a number written on one side, facing down. Assume $N$ is large, and all numbers are distinct. The deck is well suffled. We want to get the largest number.
The rules are:
1. Reveal one card at a time starting from top.
2. Stop at the current card or reveal the next card.
3. If you pass on a card, then you can't return to it.

Find a strategy with success probability $\approx \frac{1}{e} \approx 37 %$ .
Here is a strategy.

Reveal a certain proportion, say $p$ , of the cards and record the largest number $M$ you have seen.
Then stop if you see a number larger than $M$ .

Now we find the optimal $p$ . Let $X_{1}, \dots, X_{N}$ denote the numbers. Order statistics: $X_{(1)} < \dots < X_{(N)}$ .

If $M = X_{(N)}$ , $P (M = X_{(N)}) = p, P (success | M = X_{(N)}) = 0$ .

If $M = X_{(N - 1)}$ , $P (M = X_{(N - 1)}) \approx p (p - 1)$ , $P (success | M = X_{(N - 1)})$ .

If $M = X_{(N - 2)}$ , $P (M = X_{(N - 2)}) \approx p (1 - p)^{2}$ , $P (success | M = X_{(N - 2)}) = \frac{1}{2}$ .

General case: $P (M = X_{(N - k)}) \approx p (1 - p)^{2}$ , $P (success | M = X_{(N - k)}) = \frac{1}{k}$ .

So $P (success) = \sum_{k = 1}^{(1 - p) N} p (1 - p)^{k} (\frac{1}{k}) \approx - p \ln p,$ which is maximized when $p = e^{- 1}$ .

1 Basics of DTMC

Discrete-Time Markov Chain (DTMC)

${X_{n}, n \in N_{0}}$ . State space $S$ discrete. Then Markov Chain satisfies for all $n \in N, s \in S$ $P (X_{n + 1} = s_{n + 1} | X_{0} = s_{0}, \dots, X_{n} = s_{n}) = P (X_{n + 1} = s_{n + 1} | X_{n} = s_{n}) .$

For example, 1d random walk.

Transition probability $P (X_{n + 1} = j | X_{n} = i)$ .
Homogeneous if transition probability is irrelevant of $n$ . Denote $p_{i j} = P (X_{n + 1} = j | X_{n} = i)$ .
Transition matrix $P = (p_{i j})_{i, j \in S}$ .
For every $i \in S$ , $\sum_{j \in S} P (X_{n + 1} = j | X_{n} = i) = 1,$ i.e. row sum is $1$ for every row.
$P (X_{n} = j) = \sum_{i \in S} p_{i j} P (X_{n - 1} = i) . $ $ I f w e d e n o t e r a w v e c t o r $ {\vec{u}}_{n} = (P (X_{n} = i))_{i \in S} $, t h e n $ {\vec{u}}_{n} = {\vec{u}}_{n - 1} P \Rightarrow {\vec{u}}_{n} = {\vec{u}}_{0} P^{n} $ .$

Claim (Chapman-Kolmogorov Equation)

$\forall n, m \in N$ , $p_{i j}^{(m + n)} = \sum_{k \in S} p_{i k}^{(m)} p_{k j}^{(n)}$ . I.e. $(P^{n + m})_{i j} = (P^{n} P^{m})_{i j}$ .

This claim shows that the $n$ -step $P^{n}$ is actually the matrix product.

A graphical representation of a homogeneous Markov chain:
Pasted image 20241201180808.png

Some questions of interest: given $X_{0} = i \in {1, \dots, L - 1}$ ,

What is the probability of hitting $0$ before hitting $L$ ?

How long does it take?

How many times is state $j$ visited?

2 Classification of States

Accessible & Intercommunicate States

$i \to j$ : state $j$ is accessible from $i$ if $p_{i j}^{(n)} > 0$ for some $n \in N$ .
$i \leftrightarrow j$ : states $i, j$ are intercommunicate if $i \to j, j \to i$ .

$\leftrightarrow$ defines an equivalence relation.

The state space $S$ can be partitioned into equivalance classes of $\leftrightarrow$ .

A subset $C \subset S$ is called irreducible if $i \leftrightarrow j$ for all $i, j \in C$ . $C$ is a strongly connected component (SCC). A Markov Chain is said to be irreducible if $i \leftrightarrow j, \forall i, j \in S$ .

Some Important Values

First passage probability $f_{i j}^{(n)} = P (X_{1} \neq j, \dots, X_{n - 1} \neq j, X_{n} = j | X_{0} = i)$ .
Return probability $f_{i i} = \sum_{n = 1}^{\infty} f_{i i}^{(n)}$ . (probability of finally coming back)
Mean recurrence time $r_{i} = \sum_{n = 1}^{\infty} n f_{i i}^{(n)}$ . (expected time of coming back)

State Definitions

A state $i \in S$ is called

Recurrent/persistent if $f_{i i} = 1$ .
1. Null recurrent if $r_{i} = \infty$ .
2. Positive recurrent if $r_{i} < \infty$ .
Transient if $f_{i i} < 1$ .

Theorem

$\sum_{n = 1}^{\infty} p_{j j}^{(n)} = \infty \Leftrightarrow$ $j$ is recurrent $\Rightarrow \forall i \in S$ s.t. $i \to j$ , $\sum_{n = 1}^{\infty} p_{i j}^{(n)} = \infty$ .
Recurrent is equivalent to visiting the state in infinitely many times.
$\sum_{n = 1}^{\infty} p_{j j}^{(n)} < \infty \Leftrightarrow$ $j$ is transitent $\Rightarrow \forall i \in S$ . $\sum_{n = 1}^{\infty} p_{i j}^{(n)} < \infty$ and $lim_{n \to \infty} p_{i j}^{(n)} = 0$ .

3 Hitting and Recurrence

Suppose $S = \underset{B, transient states}{\underset{⏟}{{1, \dots, m}}} \cup \underset{A, absorbing}{\underset{⏟}{{m + 1, \dots, n}}}$ . We can't return from $A$ to $B$ (such $A$ are defined as absorbing states, and $B$ are transient). Then transition matrix can be written as $P = [\begin{matrix} Q & R \\ O & S \end{matrix}] .$

Hitting Probability

For $i \in B, j \in A$ , $h_{i j} = P (enters A through j \in A | X_{0} = i)$ .

Claim

$h_{i j} = p_{i j} + \sum_{k \in B} p_{i k} h_{k j} .$

Proof: First-Step Analysis

$h_{i j} = \sum_{k \in S} P (hit j \in A | X_{0} = i, X_{1} = k) P (X_{n} = k | X_{0} = i) .$

Green part: $p_{i k}$ . Yellow part: $P (hit j \in A | X_{1} = k) = {\begin{aligned} δ_{j k}, k \in A, \\ h_{k j}, k \in B . \end{aligned}$

In Matrix form, $H = (h_{i j})$ satisfies $H = R + Q H$ . Then if $(I - Q)^{- 1}$ exists, $H = (I - Q)^{- 1} R$ .

Lemma

Suppose $M$ is a square matrix with $lim_{n \to \infty} M^{n} = 0$ . Then $(I - M)^{- 1}$ exists and $(I - M)^{- 1} = \sum_{i = 0}^{\infty} M^{n}$ .

Proof

$\begin{matrix} (*) & (I - M) (I + M + \dots + M^{n - 1}) = I - M^{n} . \end{matrix}$

So taking determinant: $\begin{matrix} (**) & det (I - M) det (I + M + \dots + M^{n - 1}) = det (I - M^{n}) . \end{matrix}$
Determinant is a continuous function, so $\begin{aligned} lim_{n \to \infty} det (I - M^{n}) = det (lim_{n \to \infty} (I - M^{n})) = det (I) = 1. \\ \Rightarrow & det (I - M^{n}) > 0, \exists n . \end{aligned}$
Plug this to (**), we have $det (I - M) \neq 0$ , then $(I - M)^{- 1}$ exists.

Back to $(I - Q)^{- 1}$ . Since $P^{n} = [\begin{matrix} Q^{n} & * \\ O & S^{n} \end{matrix}] \Rightarrow p_{i k}^{(n)} = q_{i k}^{(n)} .$
$k$ transient $\Rightarrow lim_{n \to \infty} p_{i k}^{(n)} = 0 \Rightarrow lim_{n \to \infty} Q^{n} = 0$ . So by lemma, $(I - Q)^{- 1}$ exists.

Fundamental Matrix

$(I - Q)^{- 1} = \sum_{i = 0}^{\infty} Q^{n}$ is called the fundamental matrix of the absorbing Markov Chain.

Claim (Hitting Time)

Let $t_{i}$ be expected number of steps it takes to hit $A$ given $X_{0} = i \in B$ . Then $[\begin{matrix} t_{1} \\ t_{2} \\ ⋮ \\ t_{m} \end{matrix}] = (I - Q)^{- 1} [\begin{matrix} 1 \\ 1 \\ ⋮ \\ 1 \end{matrix}] .$

Proof

First, note that $t_{i} = \sum_{j \in B} t_{i j}$ , where for $i, j \in B$ , $\begin{aligned} t_{i j} & = E [\sum_{n = 0}^{\infty} 1 {X_{n} = j} | X_{0} = i] \\ = \sum_{k \in S} \underset{{\begin{aligned} δ_{i j}, k \in A \\ δ_{i j} + t_{k j}, k \in B \end{aligned}}{\underset{⏟}{E [\sum_{n = 0}^{\infty} 1 {X_{n} = j} | X_{0} = i, X_{1} = k]}} \underset{p_{i k}}{\underset{⏟}{P (X_{1} = k | X_{0} = i)}} \\ = \sum_{k \in S} δ_{i j} p_{i k} + \sum_{k \in B} t_{k j} p_{i k} = δ_{i j} + \sum_{k \in B} q_{i k} t_{k j} . \end{aligned}$
In matrix form $T = (t_{i j})$ , we have $T = I + Q T \Rightarrow T = (I - Q)^{- 1}$ . So $t_{i}$ is $i$ th row of $(I - Q)^{- 1} [1, \dots, 1]^{T}$ .

4 Stationary Distribution

Stationary Distribution

The row vector $π = (π_{i})_{i \in S}$ is called a stationary distribution of the Markov Chain with transition probability matrix $P$ , if

$π_{i} \geq 0, \forall i \in S, \sum_{i \in S} π_{i} = 1$ .
$π P = π$ . (i.e. $π$ is the left eigenvector of $P$ with eigenvalue $1$ .)

If $X_{0} \sim π$ , then $X_{n} \sim π, \forall n \in N$ .

Does every Markov Chain has a stationary distribution? When it exists, is it unique?

Theorem (Perron-Frobenius)

Every Markov Chain with finite $S$ has a stationary distribution $π$ .
If in addition the chain is irreducible, then $π$ is unique, and $π_{i} = r_{i}^{- 1}, \forall i \in S$ , where $r_{i} = \sum_{i = 1}^{\infty} n f_{i i}^{(n)}$ is the mean recurrence time for state $i \in S$ .